#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<windows.h>

//6.1 结构体设计
//6.1.1 问题表示与存储
#define TRUE 1
#define FALSE 0
typedef int STATUS;
#define MAXCHROMLENGTH 250
typedef struct
{
    int chrom[MAXCHROMLENGTH];
    int length;
    double fitness;
}INDIVIDUAL;

//6.1.2 数学函数
double f(double x0,double x1)
{
    double y;
    x0=3.14159/180*x0;
    x1=3.14159/180*x1;
    y=sin(x0)+sin(x1);
    return y;
}

//6.1.3 抽象函数
double fun(double *xs,double (f)())
{
    return f(xs[0],xs[1]);
}

//6.1.4 对数据进行二进制编码
void Coding(int code[],int *lamda,double *x,double *xmin,double *xmax)
//按区间[xmin,xmax]和二进制编码的长度lamda对数据x进行二进制编码
{
    int i,count;
    double delta;
    for(i=0;i<*lamda;i++)   code[i]=0;
    delta=(*xmax-*xmin)/(pow(2,*lamda)-1);
    count=(int)((*x-*xmin)/delta+0.5);
    i=0;
    while(count)
    {
        code[i++]=count%2;
        count=count/2;
    }
}

//6.1.5 对二进制编码进行解码成数据
void Decoding(int code[],int *lambda,double *x,double *xmin,double *xmax)
{
    int i,pw=1;
    double delta;
    delta=(*xmax-*xmin)/(pow(2,*lambda)-1);
    *x=0;
    for(i=0;i<*lambda;i++)
    {
        *x=*x+code[i]*pw;
        pw=pw*2;
    }
    *x=*x*delta+*xmin;
}

//6.1.6 染色体个体的编码【对多变量进行统一的二进制染色体编码，多变量形成一条染色体】
void ChromCoding(INDIVIDUAL *indi,int num,double *xs,int *lamdas,double *xmins,double *xmaxs,double (*fun)())
{
    int i,j,k,maxlamda=0;
    int *code;
    indi->fitness=fun(xs,f);
    indi->length=0;
    for(i=0;i<num;i++)
    {
        indi->length+=lamdas[i];
        if(maxlamda<lamdas[i])  maxlamda=lamdas[i];
    }
    code=(int*)malloc(maxlamda*sizeof(int));
    j=0;
    for(i=0;i<num;i++)
    {
        Coding(code,lamdas++,xs++,xmins++,xmaxs++);
        for(k=0;k<(*lamdas-1);k++,j++)  indi->chrom[j]=code[k];
    }
    free(code);
}

//6.1.7 染色体个体的解码【将一条染色体解码成多个变量】
void ChromDecoding(INDIVIDUAL *indi,int num,double *xs,int *lamdas,double *xmins,double *xmaxs)
{
    int i,lamda=0;
    for(i=0;i<num;i++)
    {
        Decoding(indi->chrom+lamda,lamdas++,xs++,xmins++,xmaxs++);
        lamda+=*(lamdas-1);
    }
}

//6.2 初始化染色体种群及其适应值的评估
//6.2.1 多变量初始化为一个种群
void InitPopulation(int popsize,INDIVIDUAL population[],int num,int *lamdas)
{
    int i,j,chromlength=0;
    for(i=0;i<num;i++)   chromlength+=lamdas[i];
    srand((unsigned)time(NULL));
    for(i=0;i<popsize;i++)
    {
        population[i].length=chromlength;
        for(j=0;j<chromlength;j++)
        {
            population[i].chrom[j]=(rand()%10<5)?0:1;
        }
    }
}

//6.2.2 计算每条染色体的适度值函数
void EvaluateIndividual(INDIVIDUAL *indi,int num,int *lamdas,double *xmins,double *xmaxs,double (*fun)())
{
    double *xs;
    xs=(double*)malloc(num*sizeof(double));
    ChromDecoding(indi,num,xs,lamdas,xmins,xmaxs);
    indi->fitness=fun(xs,f);
    free(xs);
}

//6.2.3 计算种群中每条染色体的适度值函数，即种群中每个个体函数值
void EvaluatePopulation(int popsize,INDIVIDUAL population[],int num,int *lamdas,double *xmins,double *xmaxs,double (*fun)())
{
    int i;
    for(i=0;i<popsize;i++)
    {
        EvaluateIndividual(population+i,num,lamdas,xmins,xmaxs,fun);
    }
}

//6.3 染色体种群最优个体和当前最优个体
//6.3.1 获取种群中最优的染色体个体
void GetBestIndividual(int popsize,INDIVIDUAL population[],INDIVIDUAL *bestindividual)
{
    int i;
    *bestindividual=population[0];
    for(i=1;i<popsize;i++)
    {
        if(population[i].fitness>bestindividual->fitness)
        {
            *bestindividual=population[i];
        }
    }
}

//6.3.2 在每次遗传进化过程中更新当前最优个体
STATUS UpdateCurrentIndividual(INDIVIDUAL *bestindividual,INDIVIDUAL *currentbestindividual)
{
    STATUS flag=FALSE;
    if(bestindividual->fitness>currentbestindividual->fitness)
    {
        *currentbestindividual=*bestindividual;
        flag=TRUE;
    }
    return flag;
}

//6.4 遗传算子
//6.4.1 选择算子：在每次遗传进化过程中更新当前最优个体
STATUS SelectOperator(int popsize,INDIVIDUAL population[])
{
    int i,j;
    double p,sum,minfitness;
    double *prop;
    INDIVIDUAL *newpopulation;
    prop=(double*)malloc(popsize*sizeof(double));
    newpopulation=(INDIVIDUAL*)malloc(popsize*sizeof(INDIVIDUAL));
    minfitness=population[0].fitness;
    for(i=1;i<popsize;i++)
    {
        if(minfitness>population[i].fitness)   minfitness=population[i].fitness;
        prop[0]=population[0].fitness-minfitness;
        sum=population[0].fitness-minfitness;
        for(i=1;i<popsize;i++)
        {
            sum+=population[i].fitness-minfitness;
            prop[i]=prop[i-1]+population[i].fitness-minfitness;
        }
        for(i=0;i<popsize;i++)   prop[i]=prop[i]/sum;
        for(i=0;i<popsize;i++)
        {
            p=rand()%10000/10000.0;
            for(j=0;prop[j]<p;j++);
            newpopulation[i]=population[j];
        }
        for(i=0;i<popsize;i++)
        {
            population[i]=newpopulation[j];
        }
        free(prop);
        free(newpopulation);
    }
}

//6.4.2 交叉算子：根据交叉概率pc依次选取所有种群中染色体个体及其随机其他个体，并随机确定两条染色体的基因位，将该位后的所有基因依次交换，进而产生两个新个体
void CrossoverOperator(int popsize,INDIVIDUAL population[],double pc)
{
    int i,j,*index,point,temp;
    double p;
    int chromlength=population[i].length;
    index=(int *)malloc(2*popsize*sizeof(int));
    for(i=0;i<popsize;i++)      index[i]=i;
    for(i=0;i<popsize;i++)
    {
        j=rand()%(popsize-i);
        temp=index[i];
        index[i]=index[j+1];
        index[j+1]=temp;
    }
    for(i=0;i<popsize-1;i+=2)
    {
        p=rand()%1000/1000.0;
        if(p<pc)
        {
            point=rand()%(chromlength-1)+1;
            for(j=point;j<chromlength;j++)
            {
                temp=population[index[i]].chrom[j];
                population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
                population[index[i+1]].chrom[j]=temp;
            }
        }
    }
    free(index);
}

//6.4.3 变异算子：根据变异概率pm对染色体种群中所有染色体的所有基因依次进行变异，产生新染色体种群
void MutateOperator(int popsize,INDIVIDUAL population[],double pm)
{
    int i,j,chromlength;
    double p;
    chromlength=population[0].length;
    for(i=0;i<popsize;i++)
    {
        for(j=0;j<chromlength;j++)
        {
            p=rand()%1000/1000.0;
            population[i].chrom[j]=(population[i].chrom[j]==0)?1:0;
        }
    }
}

//6.5 新生代生成与进化
void GenerateNextPopulation(int popsize,INDIVIDUAL population[],double pc,double pm)
{
    SelectOperator(popsize,population);
    CrossoverOperator(popsize,population,pc);
    MutateOperator(popsize,population,pm);
}

void GA(int popsize,int num,int *lamdas,double *xmins,double *xmaxs,double pc,double pm,int generation,INDIVIDUAL *currentbestindividual,double (*fun)())
{
    int i=0;
    INDIVIDUAL *population,bestindividual,oldbestindividual;
    population=(INDIVIDUAL *)malloc(popsize*sizeof(INDIVIDUAL));
    InitPopulation(popsize,population,num,lamdas);
    EvaluatePopulation(popsize,population,num,lamdas,xmins,xmaxs,fun);
    bestindividual=population[0];
    for(i=1;i<popsize;i++)
    {
        if(population[i].fitness>bestindividual.fitness)
        {
            bestindividual=population[i];
        }
    }
    *currentbestindividual=bestindividual;
    oldbestindividual=bestindividual;
    i=0;
    while(i<generation)
    {
        GenerateNextPopulation(popsize,population,pc,pm);
        EvaluatePopulation(popsize,population,num,lamdas,xmins,xmaxs,fun);
        GetBestIndividual(popsize,population,&bestindividual);
        UpdateCurrentIndividual(&bestindividual,currentbestindividual);
        if(fabs(currentbestindividual->fitness-oldbestindividual.fitness)<1e-5)  i++;
        else
        {
            oldbestindividual=*currentbestindividual;
            i=0;
        }
    }
    free(population);
}

//6.6 主程序
void main()
{
    int num=2,lamdas[]={20,20};
    double xmins[]={0,0},xmaxs[]={720,720};
    double xs[2];
    int i,j,k,popsize=48;
    double pc=0.6;
    double pm=0.1;
    int generation=3000;
    int count=10;
    INDIVIDUAL bestindividual,currentbestindividual;
    for(i=0;i<count;i++)
    {
        GA(popsize,num,lamdas,xmins,xmaxs,pc,pm,generation,&currentbestindividual,fun);
        ChromDecoding(&currentbestindividual,num,xs,lamdas,xmins,xmaxs);
        printf("Result: ");
        for(j=0;j<num;j++)   printf("x%-d=%-10lf ",j+1,xs[j]);
        printf("y=%lf\n",currentbestindividual.fitness);
        Sleep(2000);
    }
}